//
// Created by rebeater on 3/10/21.
//

#ifndef LEETCODE_MATHEMATICS_H
#define LEETCODE_MATHEMATICS_H

#include <vector>

namespace rebeater {
void testSort(void);
class Mathematics {
 public:
  template<typename T>
  /*返回从小到大排列的a的全部质因数*/
  static std::vector<T> &getFactors(T a);

  /*快速冪指數*/
  template<typename T>
  static T pow(T x, int n) {
	if (n < 0) return 1.0 / pow(x, -n);
	double res = 1;
	while (n) {
	  if (n % 2) {
		res *= x;
	  }
	  x = x * x;
	  n >>= 1u;
	}
	return res;
  }
};

/**
 * @usage:
 *  long long a = 213123;
    auto fac = Mathematics::getFactors(a);
    for (auto &v:fac) {
        cout << v << " ";
    }
 * @tparam T
 * @param a
 * @return
 */
template<typename T>
std::vector<T> &Mathematics::getFactors(T a) {
  static std::vector<T> fact;
  for (T i = 2; i * i <= a;) {
	if (a % i == 0) {
	  a /= i;
	  fact.push_back(i);
	} else {
	  i++;
	}
  }
  fact.push_back(a);
  return fact;
}
}

#endif //LEETCODE_MATHEMATICS_H
